package programmercarl.动态规划.C51;

class Solution {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int res = 0;
        //从左到右，从下到上
        for (int i = s.length()-1; i >=0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if(j-i<=1){
                        res++;
                        dp[i][j] = true;
                    }else if(dp[i+1][j-1]){
                        res++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        boolean[][] dp = new boolean[10][10];
        System.out.println(dp[0][0]);
    }
}